V, E = 0, 0 # 顶点数量，边的数量
vertices = []    # 顶点数组
edges = [] # 存储边的邻接矩阵

# 初始化图
def initGraph(n: int) -> None:
    global V, E, edges, vertices
    # 初始化邻接矩阵
    edges = [[False] * n for _ in range(n)]
    # 初始化顶点
    V = n
    vertices = list(range(n))

# 往图中添加边
def addEdge(u: int, v: int) -> None:
    global E, edges
    edges[u][v] = edges[v][u] = True
    E += 1

# __main__

# 初始化问题定义中5个顶点的无向连通图
n = 5
initGraph(n)
addEdge(0, 1)
addEdge(0, 2)
addEdge(1, 2)
addEdge(1, 3)
addEdge(2, 4)
addEdge(3, 4)

k = 0
# color数组存储各个顶点的颜色
color = [0] * n
# done标识所有顶点是否全部着色完毕
done = False		

while not done:
    k += 1 # 选择下一个颜色
    done = True   # 假设下面的循环会将所有顶点全部着色
    for i in range(n):
        if color[i] == 0: # 若顶点未着色, 为当前顶点着色为k
            color[i] = k
            # 检查颜色是否满足不相邻的条件
            if any(edges[i][j] and color[i] == color[j] for j in range(n)):
                color[i] = 0
                done = False

# 输出每个顶点对应的颜色标签
for i, c in enumerate(color):
    print(i, ':', c)